package leetcode每日一题;

/**
 * 找到所有小于n的非负素数
 *
 * 1.暴力法   但是超时了，leetcode平台没给过
 *      if(num == 0 || num == 1) {return false;}
 *         if(num == 2) {return true;}
 *         for(int factor = 2; factor < Math.ceil(Math.sqrt(num))+1; factor++) {
 *             if(num % factor == 0) {return false;}
 *         }
 *      return true;
 *   虽然是遍历，但是做了一定的优化，因为如果一个大于num的根号的数字一定不是该num的因子，所以我们只需要遍历到
 *   [sqrt(num)] + 1,其中[]表示向上取整，但是这样的时间复杂度从O(n^2)降低到O(sqrt(n)n)，时间复杂度依然很
 *   高在999983的时候超出时间复杂度
 *
 * 对于素数的筛选，历史上有许多优秀的算法可以选择，下面我们提供两种方式来解决素数筛选的问题
 *      1. 埃氏筛
 *          在上述的筛选中实际上我们将所有的数字都是独立的看，没有考虑数与数之间的联系
 *          假设当前x为素数，则x的任意倍数都不可能为素数，由此我们可以快速筛选出一批不
 *          是素数的数
 *          // 代码实现
 *          int[] isPrime = new int[n]; // 创建一个0，1数组 0代表当前不是素数，1代表当前是素数
 *          Arrays.fill(isPrime,1); // 初始化数组的值为1，假设当前每个值都是素数
 *          int ans = 0;
 *          for(int i = 0; i < n; i++) {
 *              if(isPrime[i] == 1) {
 *                  ans++;
 *                  // 此时说明i为素数，将i的倍数的数全部改变为0
 *                  if((long) i*i < n) {
 *                      for(int j = i*i; j < n; j+=i) {
 *                          isPrime[j] = 0;
 *                      }
 *                  }
 *              }
 *          }
 *          return ans;
 *          可以计算上述算法的时间复杂度为(nloglogn)
 *
 *      2. 线性筛
 *          对于埃氏筛而言，实际上还是存在许多冗余的判断，例如45，既是3的倍数，又是5的倍数，所以45实际上被标记了
 *          两次，但是我们希望通过一次查找就将合数给筛选掉，而不会重复筛选
 *          相较于埃氏筛，我们多维护一个primes数组表示当前得到的质数集合。我们从小到大遍历，
 *          如果当前的数 xx 是质数，就将其加入primes数组。
 *          List<Integer> primes = new ArrayList<Integer>();
 *          int[] isPrime = new int[n];
 *          Arrays.fill(isPrime, 1);
 *          for (int i = 2; i < n; ++i) {
 *             if (isPrime[i] == 1) {
 *                 primes.add(i);
 *             }
 *             for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {
 *                 isPrime[i * primes.get(j)] = 0;
 *                 if (i % primes.get(j) == 0) {
 *                     break;
 *                 }
 *             }
 *          }
 *          return primes.size();

 *
 */
@SuppressWarnings("all")
public class 找到所有素数 {
    public static void main(String[] args) {
        System.out.println(getAllPrime(2));
    }

    public static int getAllPrime(int n) {
        if (n == 0 || n == 1 || n == 2) {return 0;}
        int count = 0;
        for (int num = 2; num < n; num++) {
            if (isPrime(num)) {
                count++;
            }
        }
        return count;
    }

    public static boolean isPrime(int num) {
        if (num == 0 || num == 1) {return false;}
        if (num == 2) {return true;}
        for (int factor = 2; factor < Math.ceil(Math.sqrt(num))+1; factor++) {
            if (num % factor == 0) {return false;}
        }
        return true;
    }
}

